"""力扣 1013"""
"""
给你一个整数数组 arr，只有可以将其划分为三个和相等的 非空 部分时才返回 true，否则返回 false。

形式上，如果可以找出索引 i + 1 < j 且满足
 (arr[0] + arr[1] + ... + arr[i] == 
 arr[i + 1] + arr[i + 2] + ... + arr[j - 1] == 
 arr[j] + arr[j + 1] + ... + arr[arr.length - 1]) 
 就可以将数组三等分。
"""
"""
示例 1：

输入：arr = [0, 2, 1, -6, 6, -7, 9, 1, 2, 0, 1]
输出：true
解释：0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1

示例 2：

输入：arr = [0, 2, 1, -6, 6, 7, 9, -1, 2, 0, 1]
输出：false

示例 3：

输入：arr = [3, 3, 6, 5, -2, 2, 5, 1, -9, 4]
输出：true
解释：3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4
"""


def solution(arr):
    txt = "该数组没有找到和相等的三个部分"
    li1, li2, li3 = [], [], []
    s = sum(arr)
    if s % 3 != 0:
        return txt
    t = s // 3
    n, i, c = len(arr), 0, 0  # n: 数组的长度 i: 索引 c: 前n部分的和
    while i < n:
        c += arr[i]
        li1.append(arr[i])
        if c == t:  # 找到第一部分
            break
        i += 1
    if c != t:
        return txt
    j = i + 1  # 第二部分起始索引
    while j + 1 < n:  # 第三部分不能为空
        c += arr[j]
        li2.append(arr[j])
        if c == t * 2:
            break  # 找到第二部分
        j += 1
    if c != t * 2:
        return txt
    k = j + 1
    li3 = arr[k:]  # 最后一部分
    return li1, li2, li3


if __name__ == '__main__':
    li = [0, 2, 1, -6, 6, -7, 9, 1, 2, 0, 1]
    print(solution(li))
